#include "Platform/Platform.h"
#include "RedBlackTree.h"

XRBNode g_NilNode;

RBTree RBNil = &g_NilNode;

RBTree RBSearch(RBTree pTree, const char* pszName)
{
    RBTree pNode = pTree;

    while (pNode != RBNil)
    {
        int nRetCode = strcmp(pNode->pszName, pszName);
        if (!nRetCode)
            break;
        pNode = pNode->pChild[nRetCode > 0 ? LEFT : RIGHT];
    }

    return pNode;
}

BOOL RBInsert(RBTree& pTree, const char* pszName)
{
    BOOL    bResult     = false;
    RBTree  pNode       = pTree;
    RBTree  pNew        = RBNil;
    int     nRetCode    = 0;
    BOOL    bRight      = 0;

    if (pTree == RBNil)
    {
        RBInit(pTree, pszName);
        pTree->bColor = BLACK;
        goto Exit1;
    }

    nRetCode = strcmp(pNode->pszName, pszName);    
    XY_FAILED_JUMP(nRetCode);
    bRight = nRetCode > 0 ? LEFT : RIGHT;
    while (pNode->pChild[bRight] != RBNil)
    {
        pNode = pNode->pChild[bRight];
        nRetCode = strcmp(pNode->pszName, pszName);
        XY_FAILED_JUMP(nRetCode);
        bRight = nRetCode > 0 ? LEFT : RIGHT;
    }
    pNew = RBInit(pNew, pszName);
    pNode->pChild[bRight] = pNew;
    pNew->pParent = pNode;
    RBFixColor(pTree, pNew);

Exit1:
    bResult = true;
Exit0:
    return bResult;
}

BOOL RBInsert(RBTree& pTree, RBTree pNew)
{
    BOOL    bResult     = false;
    RBTree  pNode       = pTree;
    int     nRetCode    = 0;
    BOOL    bRight      = 0;

    if (pTree == RBNil)
    {
        pTree = pNew;
        pTree->bColor = BLACK;
        goto Exit1;
    }

    nRetCode = strcmp(pNode->pszName, pNew->pszName);    
    XY_FAILED_JUMP(nRetCode);
    bRight = nRetCode > 0 ? LEFT : RIGHT;
    while (pNode->pChild[bRight] != RBNil)
    {
        pNode = pNode->pChild[bRight];
        nRetCode = strcmp(pNode->pszName, pNew->pszName);
        XY_FAILED_JUMP(nRetCode);
        bRight = nRetCode > 0 ? LEFT : RIGHT;
    }

    pNode->pChild[bRight] = pNew;
    pNew->pParent = pNode;
    RBFixColor(pTree, pNew);

Exit1:
    bResult = true;
Exit0:
    return bResult;
}

void RBDelete(RBTree& pTree, RBTree pNode)
{
    RBTree  pToDel;
    RBTree  pDelChild;
    BOOL    bLorR;
    BOOL    bDelColor;

    if (pNode->pChild[LEFT] == RBNil || pNode->pChild[RIGHT] == RBNil)
    {
        pToDel = pNode;
    }
    else
    {
        pToDel = RBMin(pNode->pChild[RIGHT]);
    }

    pDelChild = pToDel->pChild[pToDel->pChild[LEFT] == RBNil];

    pDelChild->pParent = pToDel->pParent;

    bLorR = (pToDel->pParent->pChild[LEFT] != pToDel);

    pToDel->pParent->pChild[bLorR] = pDelChild;

    bDelColor = pToDel->bColor;

    if (pToDel != pNode)
    {
        BOOL bRight = (pNode == pNode->pParent->pChild[RIGHT]);
        pNode->pParent->pChild[bRight] = pToDel;
        pNode->pChild[LEFT]->pParent = pToDel;
        pNode->pChild[RIGHT]->pParent = pToDel;
        pToDel->pParent = pNode->pParent;
        pToDel->pChild[LEFT] = pNode->pChild[LEFT];
        pToDel->pChild[RIGHT] = pNode->pChild[RIGHT];
        pToDel->bColor = pNode->bColor;
    }

    if (bDelColor == BLACK)
    {
        RBDelFixColor(pTree, pDelChild);
    }
}

void RBRotate(RBTree& pTree, RBTree pNode, BOOL bRight)
{
    assert(pNode != RBNil);
    assert(pNode->pChild[!bRight] != RBNil);

    RBTree pChild = pNode->pChild[!bRight];

    pChild->pChild[bRight]->pParent = pNode;
    pNode->pChild[!bRight]          = pChild->pChild[bRight];

    pChild->pParent = pNode->pParent;

    pChild->pChild[bRight] = pNode;
    pNode->pParent = pChild;

    if (pChild->pParent == RBNil)
    {
        pTree = pChild;
    }
    else
    {
        BOOL bNodeLorR = (pChild->pParent->pChild[LEFT] != pNode);
        pChild->pParent->pChild[bNodeLorR] = pChild;
    }
}

RBTree RBInit(RBTree pNode, const char* pszName)
{
    pNode->pszName          = pszName;
    pNode->bColor           = RED;
    pNode->pChild[LEFT]     = RBNil;
    pNode->pChild[RIGHT]    = RBNil;
    pNode->pParent          = RBNil;

    return pNode;
}

void RBFixColor(RBTree& pTree, RBTree pNode)
{
    while (pNode->pParent->bColor == RED)
    {
        BOOL    bFaRight    = (pNode->pParent == pNode->pParent->pParent->pChild[RIGHT]);
        RBTree  pUncle      = pNode->pParent->pParent->pChild[!bFaRight];

        if (pUncle->bColor == RED)
        {
            pUncle->bColor = BLACK;
            pNode->pParent->bColor = BLACK;
            pNode = pNode->pParent->pParent;
            pNode->bColor = RED;
        }
        else 
        {
            BOOL bRight = (pNode == pNode->pParent->pChild[RIGHT]);

            if (bRight == bFaRight)
            {
                pNode = pNode->pParent;
                pNode->bColor = BLACK;
                pNode->pParent->bColor = RED;
                RBRotate(pTree, pNode->pParent, !bFaRight);
            }
            else
            {
                pNode = pNode->pParent;
                RBRotate(pTree, pNode, bFaRight);
            }
        }
    }
    pTree->bColor = BLACK;
}

void RBDelFixColor(RBTree& pTree, RBTree pNode)
{
    BOOL    bRight      = (pNode->pParent->pChild[LEFT] != pNode);
    RBTree  pBrother    = pNode->pParent->pChild[!bRight];

    while (pNode != pTree && pNode->bColor == BLACK)
    {
        bRight      = (pNode->pParent->pChild[LEFT] != pNode);
        pBrother    = pNode->pParent->pChild[!bRight];
        if (pBrother->bColor == RED)
        {
            pBrother->pParent->bColor = RED;
            pBrother->bColor = BLACK;
            RBRotate(pTree, pBrother, bRight);
            continue;
        }
        if (pBrother->pChild[LEFT]->bColor == BLACK && pBrother->pChild[RIGHT]->bColor == BLACK)
        {
            pBrother->bColor = RED;
            pNode = pNode->pParent;
        }
        else if (pBrother->pChild[!bRight]->bColor == BLACK)
        {
            pBrother->pChild[bRight]->bColor = BLACK;
            pBrother->bColor = RED;
            RBRotate(pTree, pBrother, !bRight);
        }
        else
        {
            pBrother->bColor = pBrother->pParent->bColor;
            pBrother->pParent->bColor = BLACK;
            pBrother->pChild[!bRight]->bColor = BLACK;
            RBRotate(pTree, pBrother->pParent, bRight);
            pNode = pTree;
        }
    }
    pNode->bColor = BLACK;
}

RBTree RBMin(RBTree pNode)
{
    assert (pNode != RBNil);
    while (pNode->pChild[LEFT] != RBNil)
    {
        pNode = pNode->pChild[LEFT];
    }
    return pNode;
}

void RBPrint(RBTree root)
{
    if (root == RBNil)
        return;

    RBPrint(root->pChild[LEFT]);
    printf("%s\n", root->pszName);
    RBPrint(root->pChild[RIGHT]);
}
